Concatenated words

Time: O(NxL^2); Space: O(NxL); medium

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example 1:

Input: words = [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”]

Output: [“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]

Explanation:

  • “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;

  • “dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;

  • “ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.

Example 2:

Input: words = [“a”,“b”,“ab”,“abc”]

Output: [“ab”]

Explanation:

  • “ab” can be concatenated by “a” and “b”.

Constraints:

  • The number of elements of the given array will not exceed 10,000

  • The length sum of elements in the given array will not exceed 600,000.

  • All the input string will only include lower case letters.

  • The returned elements order does not matter.

[1]:

class Solution1(object):
    """
    Time: O(NxL^2)
    Space: O(NxL)
    """
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        lookup = set(words)
        result = []

        for word in words:
            dp = [False] * (len(word) + 1)
            dp[0] = True
            for i in range(len(word)):
                if not dp[i]:
                    continue

                for j in range(i + 1, len(word)+1):
                    if j - i < len(word) and word[i:j] in lookup:
                        dp[j] = True

                if dp[len(word)]:
                    result.append(word)
                    break

        return result

[2]:

s = Solution1()

words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
assert s.findAllConcatenatedWordsInADict(words) == ["catsdogcats","dogcatsdog","ratcatdogcat"]

words = ["a","b","ab","abc"]
assert s.findAllConcatenatedWordsInADict(words) == ["ab"]